The present invention relates generally to the field of computer graphics and, more particularly, to methods and apparatus for merging graphic images.
Computers have become a powerful tool for the rapid and economic creation of pictures, and are particularly well suited for drafting and publishing tasks. For drafting, computer-aided design or "CAD" has found wide application. Instead of pen and paper, the CAD user employs a computer with a pointing device (typically a mouse, light pen, digitizer tablet, or the like) to create an electronic description of a drawing in the computer's memory.
For publishing, desktop publishing or "DTP" has become the standard. In DTP, both text and graphic images are manipulated on a computer screen, much as they are in CAD. In either system, when the user is satisfied with the drawing, he or she obtains a "hard copy" by sending the stored image to an output device, such as a laser printer or plotter.
In working with graphic images, it is often desirable to "acquire" images and represent them in a computer. For example, a DTP user may wish to import a photograph into a newsletter. Before an image is available to the user, however, it must be converted to a format which the computer may interpret.
Thus, the process of entering images into a computer requires that an electronic description be generated. There are two basic approaches to describing images: vector objects and bitmaps. Vector objects are mathematical descriptions of an image. For example, a line may be described by its starting and ending points. A circle may be described by its center and radius. Of particular interest to the present invention, however, are bitmap images.
In bitmaps, an image is described as a two dimensional array of bits or pixels (picture elements). By arranging combinations of black and white pixels (0 and 1 bits), a monochromatic image may be reproduced. This technique is commonly employed to reproduce images for newspapers and magazines. Bitmaps are almost always rectangular, and if the image itself is not rectangular, then the image must be rendered with a "mask" bitmap that defines the shape of the image.
While the bulk of a bitmap comprises the bits themselves, header information is also necessary to define how the bits are interpreted. This includes the height and width of the bitmap (expressed in number of pixels) and color information. In a monochromatic bitmap, one bit in the bitmap corresponds to one pixel on the display. A color bitmap requires multiple bits per pixel. In this case, the header information describes how the multiple bits correspond to particular colors. There are multiple file formats for storing bitmaps. Examples include ZSoft's PC Paintbrush (PCX), CompuServe's Graphics Interchange Format (GIF), and Microsoft's Tagged-Image File Format (TIFF).
Because bitmaps are used to store real-world images, they usually enter a computer through a scanner or a video frame grabber. A scanner converts a photographic image into a bitmapped data file; similarly, a frame grabber converts a video signal (from a video camera or VCR) to a bitmapped data file. Bitmaps can also be created by hand using computer "paint" programs, such as Microsoft's Windows.TM. Paintbrush program. Once converted into a bitmap, an image may be transferred to other computers in the same manner as other binary files (e.g., via magnetic media or modem).
Scanners, which are probably by far the most popular means for importing images, employ a light source and photodetectors to "read" or "scan" images into a computer. Two basic types are available: flatbed and handheld. The general construction and operation of each will now be briefly described.
Flatbed scanners look and operate very much like an ordinary photocopier. First, the user places an image to be scanned upon the flatbed (flat glass). Next, the scanner is activated, e.g., by pressing a button. The image is then scanned by a light source. Instead of generating a photocopy, however, the scanner focuses the image onto photodetectors which produce binary data representative of the image. Upon completion of the scan, the data are stored on a computer disk as a binary file, typically in one of the aforementioned bitmap file formats. The data file is now available to the user for use in application software, such as desktop publishing packages, paint programs, and the like.
In "handheld" scanners, on the other hand, substantially all of the scanning system is housed within a single handheld unit. Instead of placing an image to be scanned on a glass surface, as one would do with a photocopier or flatbed scanner, the image is laid face up on a flat surface, typically a desktop. The scanner, which includes a roller or wheels, is dragged across the surface of the image. The image is then recorded in a manner similar to that for flatbed systems.
While scanners allow for the easy importation of a variety of images, they have a significant limitation. Scanners, particularly handheld models, have a limited scanning area or "window" for accommodated materials to be scanned. If the image to be scanned is larger than the viewing window of the scanner, then the image cannot be captured in a single operation. In this instance, the desired image must be scanned as a series of multiple strips, i.e., portions which are small enough to fit within the viewport of the scanner. After scanning all the strips, the image may be reconstructed within the computer by manually "stitching" the strips back together (as described hereinbelow).
Before a user may stitch strips back together, other problems must be overcome. In particular, the hand scanner's reliance upon the human hand as a means for moving the unit across a source image creates artifacts. For example, strips obtained from the same image will typically have different lengths. Moreover, the geometric orientation between strips often differ in horizontal alignment (X translation), vertical alignment (Y translation), rotation, and the like. In addition, one or more strips may undergo varying rates of uniform compression and/or expansion, depending on how fast or slow the user has moved the scanner across the image. To faithfully reproduce the source image, therefore, these artifacts must be eliminated or minimized.
Even if the difficulty of artifacts is overcome, the process of stitching strips together to form the original image is cumbersome. For example, a common technique for stitching strips together requires the user to "eyeball" (i.e., judge with one's eyes) the alignment between the bitmap strips. The technique is far from perfect, however, as this requires an elaborate trial and error technique to obtain an acceptable image. In addition, the current process does not correct for the difference in documents or images because of "stretching" (transformation) due to a fast scanning speed. Moreover, the user must often manually correct for vertical skewing (rotation) of each image strip. Routinely, the user obtains a bitmap where the intersections of the strips (i.e., the stitched areas) appear rough and misaligned.
Another technique requires the use of registration marks, i.e., marks that are added to the source image that allow the software to find the marks and merge the image. The marks are generally added to an image by scanning the image with a transparency having the marks overlaid on the image. The software then finds the marks and attempts to merge the images based upon the location of the marks. Another technique employs a plastic grid to aid the user in scanning images in strips in a more consistent manner. However, none of these techniques are transparent to the user, nor are they fully automated. Moreover, these techniques rely heavily on the dexterity of the individual user in aligning images or adding registration marks to the image that the software can find and use to merge the images. The results are almost always less than satisfactory.
Thus, it is desirable to provide a system and methods which automatically align bitmap images with minimum user effort. Moreover, the methods employed should achieve precise alignment between two or more images--precision that cannot be achieved by manual positioning techniques alone. The present invention fulfills this and other needs.